package com.frx.test;


/**
 * 假设n为正整数，斐波那契数列定义为：
 * f(n) = 1, n < 3;
 * f(n) = f(n-1) + f(n-2), n>=3
 *
 * 现在请你来计算f(n)的值，但是不需要给出精确值，只要结果的后六位即可。
 *
 * 输入：一行，包含一个正整数n，且0<n<1000
 * 输出：一行，f(n)的后6位（十进制，不足6位不补零）
 * */
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class U1235p6 {

    public static void main(String []args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        long num1 = fbnq(n);
        System.out.println(num1);
    }

    public static long fbnq(int n) {
        if (n < 3) {
            return 1L;
        }
        int arr[] = new int[n];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < n; i++) {
            arr[i]=(arr[i-2]+arr[i-1])%1000000;
        }
        return arr[n-1];
    }
}
